import java.util.*;

/**
 * 827. 最大人工岛
 * https://leetcode-cn.com/problems/making-a-large-island/
 */
public class Solutions_827 {
    public static void main(String[] args) {
//        int[][] grid = {{1, 0},
//                        {0, 1}};  // output: 3
//        解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

//        int[][] grid = {{1, 1},
//                        {1, 0}};  // output: 4
//        解释: 将一格0变成1，岛屿的面积扩大为 4。

        int[][] grid = {{1, 1},
                        {1, 1}};  // output: 4
//        解释: 没有0可以让我们变成1，面积依然为 4。

//        int[][] grid = {{0, 0, 0, 0, 0, 0, 0},
//                        {0, 1, 1, 1, 1, 0, 0},
//                        {0, 1, 0, 0, 1, 0, 0},
//                        {1, 0, 1, 0, 1, 0, 0},
//                        {0, 1, 0, 0, 1, 0, 0},
//                        {0, 1, 0, 0, 1, 0, 0},
//                        {0, 1, 1, 1, 1, 0, 0}};  // output: 18

        int result = largestIsland(grid);
        System.out.println(result);
    }

    private static int row, col;
    private static int[][] direct;

    /**
     * 解法二：连通块思想 + DFS（17ms）
     */
    public static int largestIsland(int[][] grid) {
        int res = -1;
        row = grid.length;
        col = grid[0].length;
        // 四个方向：上、下、左、右
        direct = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // key：分组 id，value：分组等于 key 的陆地面积
        Map<Integer, Integer> map = new HashMap<>();
        // 分组从 2 开始标记
        int group = 2;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    // 对每块陆地进行遍历，统计面积并标记分组，加入 map 中
                    int count = dfs(grid, i, j, group);
                    map.put(group, count);
                    group ++;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 对每块海洋的上、下、左、右四个方向上的陆地分组
                if (grid[i][j] == 0) {
                    // 使用 set，防止重复计算同一分组
                    Set<Integer> set = new HashSet<>();
                    int cur = 1;
                    for (int[] dir : direct) {
                        int m = i + dir[0];
                        int n = j + dir[1];
                        if (inArea(m, n)) {
                            set.add(grid[m][n]);
                        }
                    }
                    for (int g : set) {
                        // 计算各分组对应的陆地面积
                        cur += map.getOrDefault(g, 0);
                    }
                    res = Math.max(res, cur);
                }
            }
        }
        // 没有海洋的情况，那么最大的陆地面积就是 row * col
        return res == -1 ? row * col : res;
    }

    public static boolean inArea(int i, int j) {
        return i >= 0 && j >= 0 && i < row && j < col;
    }

    public static int dfs(int[][] grid, int i, int j, int group) {
        int ans = 1;
        int m, n;
        grid[i][j] = group;
        for (int[] dir : direct) {
            m = i + dir[0];
            n = j + dir[1];
            // 上、下、左、右四个方向上，陆地的数量
            if (inArea(m, n) && grid[m][n] == 1) {
                ans += dfs(grid, m, n, group);
            }
        }
        return ans;
    }

    /**
     * 解法一：暴力法 + BFS（715ms）
     */
    public static int largestIsland2(int[][] grid) {
        // 对每个 0，都进行搜索
        row = grid.length;
        col = grid[0].length;
        // 四个方向：上、下、左、右
        direct = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int res = -1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    // 对每块海洋都进行搜索，得到“填海”后，地图上连通的岛屿面积
                    int cur = bfs(grid, i, j);
                    res = Math.max(res, cur);
                }
            }
        }
        return res == -1 ? row * col : res;
    }

    public static int bfs(int[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        queue.add(new int[]{i, j});
        // 标记为已访问
        set.add(i * row + j);

        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            ans += size;
            while (size-- > 0) {
                int[] cur = queue.poll();
                // 向上、下、左、右四个方向搜索
                for (int[] dir : direct) {
                    int m = cur[0] + dir[0];
                    int n = cur[1] + dir[1];
                    if (m >= 0 && n >= 0 && m < row && n < col) {
                        if (!set.contains(m * row + n) && grid[m][n] == 1) {
                            // [m, n] 未访问过，并且是陆地（等于 1）
                            set.add(m * row + n);
                            queue.add(new int[]{m, n});
                        }
                    }
                }
            }
        }
        return ans;
    }
}
